package com.cet.algorithm.回溯.组合总和;

import java.util.LinkedList;
import java.util.List;

/**
 * @program: cet-practice
 * @description: 组合总和
 * @author: 陈恩涛
 * @create: 2023-05-29 11:13
 **/
public class LC39 {

    // 结果集
    List<List<Integer>> result = new LinkedList<>();

    // 暂存遍历节点的集合
    LinkedList<Integer> path = new LinkedList<>();

    /**
     * 可选元素可以重复使用，返回和为target的所有组合
     * @param candidates 可选元素集合
     * @param target 目标和
     * @return 所有组合的集合
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTrace(candidates, target, 0);
        return result;
    }

    public void backTrace(int[] candidates, int target, int startIdx) {

        // 递归结束条件
        if (target < 0) {
            return;
        }

        if (target == 0) {
            result.add(new LinkedList<>(path));
            return;
        }

        // 单层递归逻辑

        for (int i = startIdx; i < candidates.length; i++) {
            if (target - candidates[i] < 0) {
                continue;
            }
            path.add(candidates[i]);
            backTrace(candidates, target - candidates[i], i);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        LC39 lc39 = new LC39();
        System.out.println(lc39.combinationSum(new int[]{2, 3, 5}, 8));
    }


}
